#include <iostream>
#include <assert.h>
#include <malloc.h>

using namespace std;
typedef enum ColorType {RED, BLACK} color_type;
typedef struct rbt_t{
    int data;
    rbt_t * left=0;
    rbt_t * right=0;
    rbt_t * parent=0;
    //父节点
    rbt_t * p=0;
    color_type color;
}rbt_t;

typedef struct rbt_root_t{
    rbt_t* root=0;
}rbt_root_t;

void rb_insert_fixup(rbt_root_t *tree,rbt_t* z_node);
void left_rotate(rbt_root_t *tree,rbt_t* point_node);
void right_rotate(rbt_root_t *tree,rbt_t* point_node);
/*
*@brief rbt_create 初始化
*/
rbt_t* rbt_t_create(int data){
    rbt_t *new_node = (rbt_t*)malloc(sizeof(rbt_t));
    new_node->data = data;
    rbt_t *l_nil = (rbt_t*)malloc(sizeof(rbt_t));
    l_nil->color=color_type::BLACK;
    rbt_t *r_nil = (rbt_t*)malloc(sizeof(rbt_t));
    r_nil->color=color_type::BLACK;
    new_node->left = l_nil;
    new_node->right = r_nil;
    new_node->parent=0;
    new_node->color = color_type::RED;
    return new_node;
}

void insert(rbt_root_t *tree,int data){
    rbt_t *new_node = rbt_t_create(data);
    if(tree->root==0){
        tree->root = new_node;
    }else
    {
        rbt_t *root = tree->root;
        rbt_t *curr = tree->root;
        rbt_t *tmp_parent;
        bool left = true;
        while (curr!=0 && curr->left!=0)
        {
            tmp_parent = curr;
            if(curr->data>data){
                curr = curr->left;
                left = true;
            }else{
                curr = curr->right;
                left = false;
            }
        }
        if(left)    {
            tmp_parent->left = new_node;
            new_node->parent = tmp_parent;
        }else{
            tmp_parent->right = new_node;
            new_node->parent = tmp_parent;
        }
    }
    rb_insert_fixup(tree,new_node);
}

void setBlack(rbt_t *node){
    node->color = color_type::BLACK;
}

void setRed(rbt_t *node){
    node->color = color_type::RED;
}
void rb_insert_fixup(rbt_root_t *tree,rbt_t* z_node){
    rbt_t* parent;
    rbt_t* grand_parent;
    while((parent=z_node->parent)!=0 && parent->color==color_type::RED){
        grand_parent = parent->parent;
        //如果父节点是祖父节点的左孩子
        if(parent == grand_parent->left){
             // Case 1条件：叔叔节点是红色
             rbt_t* uncle_node = grand_parent->right;
             if(uncle_node!=0 && uncle_node->color == color_type::RED){
                 setBlack(uncle_node);
                 setBlack(parent);
                 setRed(grand_parent);
                 z_node = grand_parent;
                 continue;
             }
              // Case 2条件：叔叔是黑色，且当前节点是右孩子
              // z_node围绕parent左旋，变成case3
              if(parent->right==z_node){
                  rbt_t* tmp_parent;
                  //围绕parent左旋
                  left_rotate(tree,parent);
                  //旋转之后 parent节点变为了z_node的子节点，所以将z_node之前的parent节点设置为当前节点
                  tmp_parent = parent;
                  parent = z_node;
                  z_node = tmp_parent;
              }
              // Case 3条件：叔叔是黑色，且当前节点是左孩子。(01) 将“父节点”设为“黑色”。
              // Case 3条件：叔叔是黑色，且当前节点是左孩子。
            setBlack(parent);
            setRed(grand_parent);
            right_rotate(tree,grand_parent);
        }else if(parent == grand_parent->right)
        {
            // Case 1条件：叔叔节点是红色
             rbt_t* uncle_node = grand_parent->left;
             if(uncle_node!=0 && uncle_node->color == color_type::RED){
                 setBlack(uncle_node);
                 setBlack(parent);
                 setRed(grand_parent);
                 z_node = grand_parent;
                 continue;
             }
             // Case 2条件：叔叔是黑色，且当前节点是左孩子
            // z_node围绕parent左旋，变成case3
            if(parent->left==z_node){
                rbt_t* tmp_parent;
                //围绕parent右
                right_rotate(tree,parent);
                //旋转之后 parent节点变为了z_node的子节点，所以将z_node之前的parent节点设置为当前节点
                tmp_parent = parent;
                parent = z_node;
                z_node = tmp_parent;
            }
            // Case 3条件：叔叔是黑色，且当前节点是右孩子。(01) 将“父节点”设为“黑色”。
            setBlack(parent);
            setRed(grand_parent);
            left_rotate(tree,grand_parent);
        }
        
    }
    // 将根节点设为黑色
    setBlack(tree->root);
}

//right_right型，point_node为旋转点
void left_rotate(rbt_root_t *tree,rbt_t* point_node){
    //围绕该点旋转
    rbt_t* z_node = point_node->right;
    point_node->right = z_node->left;
    if(z_node->left != 0){
        z_node->left->parent = point_node;
    }
    z_node->parent = point_node->parent;
    if(point_node->parent==0){
        tree->root = z_node;
    }else if (point_node->parent->right == point_node)
    {
        point_node->parent->right = z_node;
    }else if (point_node->parent->left == point_node)
    {
        point_node->parent->left = z_node;
    }
    point_node->parent = z_node;
    z_node->left = point_node;
}


//right_right型，point_node为旋转点 这是好像可用
void right_rotate(rbt_root_t *tree,rbt_t* point_node){
    //围绕该点旋转
    // rbt_t* point_node = z_node->left;
    rbt_t* z_node = point_node->left;
    point_node->left = z_node->right;
    if(z_node->right != 0){
        z_node->right->parent = point_node;
    }
    z_node->parent = point_node->parent;
    if(point_node->parent==0){
        tree->root = z_node;
    }else if (point_node->parent->right == point_node)
    {
        point_node->parent->right = z_node;
    }else if (point_node->parent->left == point_node)
    {
        point_node->parent->left = z_node;
    }
    point_node->parent = z_node;
    z_node->right = point_node;
}

int main(){
    // int arr[] = {6,5,4,3,2,1,0};
    int arr[] = {10,6,2,3,1,23,20};
    rbt_root_t *tree = (rbt_root_t*)malloc(sizeof(rbt_root_t));
    tree->root=0;
    for(int a : arr){
        insert(tree,a);
    }
    cout<<endl;
}